package com.yin.myproject.arithmetic;

/**
 * KPM字符串匹配
 *
 * @author Eason
 * @create 2018-04-25 16:00
 **/
public class KPMStringSearch {

    public static void main(String[] args) {
        KPMStringSearch kpmStringSearch = new KPMStringSearch();
        String s = "bbc abcdab abcdabcdabde";
        String p = "abcdabd";
        int kmp = kpmStringSearch.KMP(s, p);
        System.out.println(kmp);
    }

    private int[] getNext(String p) {
        char[] chars = p.toCharArray();
        int plength = chars.length;
        int i = 0;
        int j = -1;//用来计数
        int[] next = new int[plength];
        next[0] = -1;
        while (i < plength - 1) {
            if (j == -1 || chars[i] == chars[j]) {
                i++;
                j++;
                next[i] = j;
            } else {
                j = next[j];//让j=-1回到字符数组的首位置重新比较
            }
        }

        return next;
    }

    public int KMP(String origin, String pattern) {
        int[] next = getNext(pattern);

        char[] originChars = origin.toCharArray();
        char[] patternChars = pattern.toCharArray();

        int i = 0;
        int j = 0;
        int originLength = originChars.length;
        int patternLength = patternChars.length;

        while (i < originLength && j < patternLength) {
            if (j == -1 || originChars[i] == patternChars[j]) {
                i++;
                j++;
            } else {
                j = next[j];
            }
        }

        if (j == patternLength) {
            return i - j;
        }
        return -1;
    }
}
